package org.example.sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] array = {3, 8, 6, 7, 4, 2};
        System.out.println("排序前:");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }
        System.out.println();
        int[] sort = sort(array);
        System.out.println("排序后:");
        for (int i = 0; i < sort.length; i++) {
            System.out.print(sort[i] + ",");
        }
    }
//    基本原理:分而治之：将数组分为已排序和未排序两部分，初始时已排序部分只有第一个元素，
//    逐个插入：从第二个元素开始，依次将未排序元素插入到已排序部分的合适位置
//    寻找位置：在已排序部分从右往左比较，找到合适的插入位置，移动元素：将大于待插入元素的已排序元素向右移动一位
//    插入元素：将待排序元素放到找到的正确位置上
//    核心特点：逐步构建有序序列：每次将一个元素插入到前面已经排好序的序列中
//    稳定排序：相等元素的相对位置不会改变,原地排序：只需要常数级别的额外空间,适应性好：对于接近有序的数组效率较高
//    实现要点(参考提供的代码)使用 Arrays.copyOf(sourceArray, sourceArray.length) 创建数组副本，避免修改原数组
//    外层循环 for (int i = 1; i < arr.length; i++) 控制待插入元素,用变量 tmp 保存待插入元素 arr[i]
//    内层循环通过 while (j > 0 && tmp < arr[j - 1]) 从右向左查找插入位置
//    找到位置后将元素插入到正确位置 arr[j] = tmp
//    时间复杂度:最坏情况：O(n²) - 数组完全逆序,最好情况：O(n) - 数组已经有序,平均情况：O(n²)
//    空间复杂度:O(1) - 只需要常数级别的额外空间

    public static int[] sort(int[] sourceArray){
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}
